#include <atomic>

namespace dnskv {

using std::atomic;

// 一个DNSKV专用的高性能无锁链
// 外部保证只有单个线程调用get_next, go_next和erase_next接口
template<typename T>
class LinkList {
    struct Entry {
        T e;
        Entry * next;
        Entry(T & a) : e(a) {}
    };

public:
    std::atomic<Entry *> head_;
    Entry * cur_;

    LinkList() {
        head_.store(nullptr);
        cur_ = nullptr;
    }

    void push_front(T & a) {
        Entry * expected = head_.load(std::memory_order_relaxed);
        Entry * new_head_ = new Entry(a);
        do {
            new_head_->next = expected;
        } while(head_.compare_exchange_weak(expected, new_head_, std::memory_order_release, std::memory_order_relaxed));

        if(cur_ == nullptr) { // 如果cur为空，那么将它指向头部
            cur_ = new_head_;
        }
    }

    T get_next() { // 返回当前的下一个元素
        if(cur_->next == nullptr) {
            cur_ = head_.load(std::memory_order_relaxed); // 将cur_指向新的头部
        }
        return cur_->next->e;
    }

    T go_next() { // 往前走一步，并且get_next
        cur_ = cur_->next;
        return get_next();
    }

    void erase_next() { // 删除cur_的下一个元素
        Entry * old = cur_->next;
        cur_->next = cur_->next->next;
        delete old;
    }
};
    
} // namespace dnskv